package com.autumn.algorithm;

/**
 * 删除排序链表中的重复元素
 * 存在一个升序排列的链表，给定此链表的头节点 head，
 * 需删除所有重复的元素，使每个元素仅出现一次
 */
public class Algorithm08DelDuplicates {
    /**
     * 解法一：遍历
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode currentNode = head;
        while (null != currentNode.next) {
            if (currentNode.next.val == currentNode.val) {
                currentNode.next = currentNode.next.next;
            } else {
                currentNode = currentNode.next;
            }
        }
        return head;
    }

    /**
     * 解法二：递归
     * 本质是将列表压栈后倒序处理
     * 时间复杂度 O(n)
     * 空间复杂度 高于解法一
     */
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        head.next = deleteDuplicates2(head.next);
        return head.val == head.next.val ? head.next : head;
    }
}
